package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/remove-nth-node-from-end-of-list/">删除链表的倒数第N个节点</a>
 *
 * @author zhenzicheng
 * @date 2022-06-21 14:40
 */
public class RemoveNthNodeFromEndOfList_19 {

  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode temp = new ListNode(-1); // 新的节点
    ListNode slow = temp, fast = temp; // 快慢指针
    temp.next = head; // 连接头结点

    while (n-- > 0) {
      fast = fast.next;
    }
    // 快指针再一次往下走一位，为了让后面慢指针走向要返回的头结点之前的一个节点位置

    while (fast.next != null) {
      slow = slow.next;
      fast = fast.next;
    }
    // 删除节点
    slow.next = slow.next.next;

    return temp.next;
  }
}
